package com.zp.self.module.level_4_算法练习.算法.动态规划;

import java.util.Arrays;

/**
 * @author By ZengPeng
 */
public class 力扣_62_不同路径 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_62_不同路径().uniquePaths(3,7));
//        System.out.println(new 力扣_62_不同路径().uniquePaths(3,2));
//        System.out.println(new 力扣_62_不同路径().uniquePaths(7,3));
//        System.out.println(new 力扣_62_不同路径().uniquePaths(3,3));
//        System.out.println(new 力扣_62_不同路径().uniquePaths(2,2));
//        System.out.println(new 力扣_62_不同路径().uniquePaths(10,1));
//        System.out.println(new 力扣_62_不同路径().uniquePaths(1,1));
//        System.out.println(new 力扣_62_不同路径().uniquePaths(100,80));
    }

    /**
    题目：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
     机器人每次只能【向下或者向右移动】一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
     问总共有多少条不同的路径？

     示例 1：
     输入：m = 3, n = 7
     输出：28

     示例 2：
     输入：m = 3, n = 2
     输出：3
     解释：
     从左上角开始，总共有 3 条路径可以到达右下角。
     1. 向右 -> 向下 -> 向下
     2. 向下 -> 向下 -> 向右
     3. 向下 -> 向右 -> 向下

     示例 3：
     输入：m = 7, n = 3
     输出：28

     示例 4：
     输入：m = 3, n = 3
     输出：6

    分析：【P ❤❤❤】阿这,这就是动态规划啦？！！！我还以为多难呢 【年轻人，不要太膨胀】
       1.递归、用二位数组记住每个节点的可能次数 numb[][]
            fun(n,m) =  fun(n+1,m) + fun(n,m+1)
            --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
       2.动态规划：从小的方向开始，不用倒退的方式
                    初始化第一行、第一列 = 1
            --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
       2.1动态规划：优化为一维数组
       3.数学--排列组合【组合】：到达m,n 将向下移动m-1次，向右移动n-1次，总计：m+n-2次
                                m+n-2次移动中，有m-1次向下移动。则在m+n-2次移动中挑出向下移动m-1的可能情况：C（（m+n-2），（m-1））
                        如：3，4  总移动5次 ：↓↓→→→
                            转换为：编号1，2，3，4，5的篮子，要放入2个乒乓球，3个篮球，问有多少种方式？
                            将两个乒乓放入5个篮子，篮球的位置就固定了，且乒乓球没有区分【如果每个球有A、B、C编号，则是排列问题了】
                            故：此时是组合问题，有C(5,2)种方式 =10

    边界值 & 注意点：
       1.
     **/
    public int uniquePaths(int m, int n) {
        //3.数学--排列组合【组合】C((m+n-2),(m-1))
        int all = m + n -2 ;
        m = Math.min(m,n);
        int up=all-m+2,down=1;
        long res=1;
        while (down<m){
            res=res*up/down;
            down++;up++;
        }
        return (int)res;

        //2.动态规划：从小的方向开始，不用倒退的方式
       /* int[][] numb = new int[m][n];
        for (int i = 0; i < m; i++)//初始化第一行
             numb[i][0]=1;
        for (int i = 0; i < n; i++)//初始化第一列
            numb[0][i]=1;
        for (int x = 1; x < m; x++) {
            for (int y = 1; y < n; y++)
               numb[x][y]=numb[x-1][y]+numb[x][y-1];
        }
        return  numb[m-1][n-1];*/

        //1.递归、用二位数组记住每个节点的可能次数 numb[][]
       /* int[][] numb = new int[m][n];
        return recursion(0,0,numb);*/
    }

    //2.1动态规划：优化为一维数组
    public int uniquePaths2(int m, int n) {
        int[] cur = new int[n];
        Arrays.fill(cur,1);
        for (int i = 1; i < m;i++){
            for (int j = 1; j < n; j++){
                cur[j] += cur[j-1] ;
            }
        }
        return cur[n-1];
    }
    private int recursion(int m, int n, int[][] numb) {
        if(numb[m][n]!=0) return numb[m][n];
        if(m==numb.length-1 && n==numb[0].length-1) return 1;
        int sum = 0;
        if(m<numb.length-1)
            sum +=  recursion( m+1,  n,  numb);
        if(n<numb[0].length-1)
            sum +=  recursion( m, n+1,  numb);
        numb[m][n] =sum;
        return sum;
    }
}
